The main purpose of this paper is to show that we can exploit the difference ($l_1$-norm and $l_2$-norm) in the probability calculation between quantum and probabilistic computations to claim the difference in their space efficiencies. It is shown that there is a finite language $L$ which contains sentences of length up to $O(n^{c+1})$ such that: ($i$) There is a one-way quantum finite automaton (qfa) of $O(n^{c+4})$ states which recognizes $L$. ($ii$) However, if we try to simulate this qfa by a probabilistic finite automaton (pfa) \textit{using the same algorithm}, then it needs $\Omega(n^{2c+4})$ states. It should be noted that we do not prove real lower bounds for pfa's but show that if pfa's and qfa's use exactly the same algorithm, then qfa's need much less states.
展开▼
机译：本文的主要目的是表明，我们可以利用量子计算和概率计算之间的概率计算中的差异（$ l_1 $-范数和$ l_2 $-范数）来主张其空间效率上的差异。结果表明，存在一种有限语言$ L $，其中包含的句子的长度最大为$ O（n ^ {c + 1}）$，使得：（$ i $）存在单向量子有限自动机（qfa $ O（n ^ {c + 4}）$的）表示可以识别$ L $。 （$ ii $）但是，如果我们尝试通过概率有限自动机（pfa）\ textit {使用同一算法}模拟此qfa，则它需要$ \ Omega（n ^ {2c + 4}）$状态。应该注意的是，我们并没有证明pfa的真正下界，而是表明如果pfa和qfa使用完全相同的算法，则qfa所需要的状态要少得多。
展开▼
